package choosers;

import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author Glen Edmonds Awesome algorithm
 * 
 */
public class Choosers {
	private static class Node {
		boolean left;
		int leftNode;
		int rightNode;

		public Node(String nodeString) {
			String[] parts = nodeString.split(" ");
			this.left = parts[0].equals("L");
			this.leftNode = parts[1].equals("X") ? -1 : Integer
					.parseInt(parts[1]);
			this.rightNode = parts[2].equals("X") ? -1 : Integer
					.parseInt(parts[2]);
		}
	}

	private Node[] nodes;

	private Set<Integer> states = new HashSet<Integer>();

	public int length(String[] nodesSpec, int start) {
		nodes = new Node[nodesSpec.length];
		for (int i = 0; i < nodes.length; i++)
			nodes[i] = new Node(nodesSpec[i]);

		for (int moves = 1, next = start;; moves++) {
			if (!states.add(fingerprint(next)))
				return -1;
			next = move(next);
			if (next == -1)
				return moves;
		}
	}

	/**
	 * @param next
	 * @return the next node to be at after this move
	 */
	private int move(int next) {
		Node node = nodes[next];
		node.left = !node.left;
		return node.left ? node.rightNode : node.leftNode;
	}

	/**
	 * @param next
	 * @return a unique fingerprint of the state of all node switches
	 */
	private Integer fingerprint(int next) {
		// Turn bits on result if set left
		int result = next;
		for (int i = 0; i < nodes.length; i++) {
			result <<= 1;
			result |= nodes[i].left ? 1 : 0;
		}
		return result;
	}

	public static void main(String[] args) {
		assertCorrect(1, new String[] { "L 1 2", "R 2 0", "L X X" }, 0, 4);
		assertCorrect(2, new String[] { "L 1 2", "R 2 0", "L X X" }, 2, 1);
		assertCorrect(3, new String[] { "L 0 0" }, 0, -1);
		System.out.println("All tests passed");
	}

	private static void assertCorrect(int testNumber, String[] game, int start,
			int expected) {
		Choosers chooser = new Choosers();
		int actual = chooser.length(game, start);
		if (actual != expected)
			throw new IllegalStateException("Inforrect result for test "
					+ testNumber);
	}
}
